package 字节;
/*
分治 时间复杂度最好最坏都是log(n log n )
空间复杂度为log(log n)
 */
public class 快速排序 {
    static void quicksort(int[] a,int left,int right){
        if (left<right){
            int index=getIndex(a,left,right);
            quicksort(a,left,index-1);
            quicksort(a,index+1,right);
        }
    }

    static int getIndex(int[] a,int left,int right){
        int compare=a[left];
        while (left<right){
            while (left<right&&a[right]>=compare){
                right--;
            }
            a[left]=a[right];
            while (left<right&&a[left]<=compare){
                left++;
            }
            a[right]=a[left];
        }
        a[left]=compare;
        return left;
    }

    public static void main(String[] args) {
        int[] arr={1,4,32,6,9,4};
        quicksort(arr,0,arr.length-1);
        for (int i : arr) {
            System.out.println(i);
        }
    }


}
